Data about an image, a voice, a sensor, etc. or feature quantities extracted from the data are multiplied by a matrix having random numbers as its elements, so as to generate compressed data. The number of elements of data which is subjected to dimensional compression is called dimensionality. In conventional dimensional compression, the elements of an m×n matrix are set to real values, and the matrix is constructed by using values selected at random as the elements. n is the dimensionality of original data and m is the dimensionality of the data after compression. Further, n≧m.
By compressing data about an image, a voice, a sensor, etc. or feature quantities of the data in the above-mentioned way, the amount of data to be processed which are associated with a search, recognition, prediction, or the like is reduced and a speedup is implemented, so that a single operation can be processed in a short time and many operations or a more-complicated operation can be implemented within a certain fixed time period.
For example, an image matching system shown in FIG. 4 searches for an image close to a photo (search image 101) captured by a terminal device 100, or the like from among many sample images held by an image database (referred to as DB from here on) 201 of a server device 200. In this system, a feature quantity extracting unit 102 of the terminal device 100 extracts feature quantities from the search image 101. When SIFT (Scale-Invariant Feature Transform) is used for the feature quantity extraction, a plurality of 128-byte feature quantity vectors (typically, several tens to hundreds of feature quantity vectors) are extracted per image.
A conventional dimensional compression unit 103 performs dimensional compression on the above-mentioned feature quantities by using a random projection matrix. The random projection matrix used at that time is given by equation (1), and the elements a(r, c) of the random projection matrix are a(r, c) to N (0, 1) and are pursuant to a normal distribution having an average of 0 and a variance of 1.AεRm×n  (1)
When the feature quantities are expressed by x=(x1, x2, . . . , xn), the feature quantities y=(y1, y2, . . . , ym) after compression are calculated according to yT=AxT. “T” of yT and xT means transposition.
When SIFT is used as mentioned above, each element xi of the feature quantity vector x is represented as 1 byte=8 bits, and the feature quantity vector is expressed as n=128. Further, when each element a(r, c) of the random projection matrix A is configured in such a way as to be able to be represented as 8 bits, each element yk of the feature quantity vector y after compression can be calculated according to equation (2).yk=x1·a(k,1)+x2·a(k, 2)+ . . . +xi·a(k,i)+ . . . +xn·a(k,n)  (2)
Therefore, because 128=27 elements whose number is equal to the number of columns are added to 2 bytes=16 bits in the multiplication of the elements of the random projection matrix A and the elements of the feature quantity vector x, a maximum of 16+7=23 bits is the quantization size of each element yk of the feature quantity vector y after compression. The length of the feature quantity vector y after compression can be expressed as an m-dimensional vector, and the data can be compressed from 128 before compression to 40 when the dimension is set to m=40.
In addition, in nonpatent reference 1, a method of reducing the quantization size of each element yk of the feature vector y after compression is examined. For example, a method of compressing the size of each element yk from a maximum of 23 bits to about 1 to 5 bits in the above-mentioned example is shown. In this method, the dimensional compression is performed on the condition that the distance between feature quantities is maintained.
In the case in which the quantization size reducing unit 104 compresses the quantization size of feature quantities by using the method disclosed in above-mentioned nonpatent reference 1, when the amount of data in which each feature quantity has 128×8=1,024 bits is compressed to m=40 and the quantization size of 4 bits, the amount of data after compression is 128×40/128×4=160 bits and the amount of data is compressed to 160/1,024=15.6%.
Also in the server device 200, the feature quantity extracting unit 102 extracts feature quantities from each sample image stored the image DB 201, and the dimensional compression unit 103 and the quantization size reducing unit 104 compress the feature quantities.
For example, when the image DB 201 has 10,000 sample images, the server device 200 performs feature quantity extraction and data compression on each sample image, and the searcher 205 compares the compressed feature quantities of the search image 101, which are sent from the terminal device 100, with the image DB, to search for a sample image close to the search image 101.